package leetcode.simple.q349;

import leetcode.util.TimeUtils;

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int[] nums1 = {1,2,2,1};
        int[] nums2 = {2,2};

        intersect2(nums1, nums2);
    }

    /**
     * 我自己写的代码
     * 输入: nums1 = [1,2,2,1], nums2 = [2,2]
     * 输出: [2]
     * 输入: nums1 = [3, 1, 2], nums2 = [1,1]
     * 输出: [1]
     * @param nums1
     * @param nums2
     * @return
     */
    public static int[] intersect(int[] nums1, int[] nums2) {
        Set<Integer> set = new HashSet<>();
        int[] result;
        int arrLen1 = nums1.length;
        int arrLen2 = nums2.length;
        //如果数组1长度比数组2长度小
        //先选择长度小的数组作为基础数组，长度长的数组用来遍历，遍历的每个元素进行比对
        if (arrLen1 <= arrLen2){
            for (int i = 0; i < arrLen2; i++) {
                for (int j = 0; j < arrLen1; j++) {
                    if (nums2[i] == nums1[j]){
                        set.add(nums1[j]);
                        break; //是否可以停掉？
                    }
                }
            }
        }else {
            for (int i = 0; i < arrLen1; i++) {
                for (int j = 0; j < arrLen2; j++) {
                    if (nums1[i] == nums2[j]){
                        set.add(nums2[j]);
                        break; //是否可以停掉？
                    }
                }
            }
        }
        List<Integer> list = new ArrayList<>(set);
        result = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            result[i] = list.get(i);
        }

        return result;
    }

    /**
     * 我自己写的代码2
     * 输入: nums1 = [1,2,2,1], nums2 = [2,2]
     * 输出: [2]
     * 输入: nums1 = [3, 1, 2], nums2 = [1,1]
     * 输出: [1]
     * @param nums1
     * @param nums2
     * @return
     */
    public static int[] intersect2(int[] nums1, int[] nums2) {
        //先把2个数组放到集合中
        Set<Integer> set1 = new HashSet<>();
        for (Integer n : nums1) {
            set1.add(n);
        }

        Set<Integer> set2 = new HashSet<>();
        for (Integer n : nums2) {
            set2.add(n);
        }

        //遍历
        int result[];
        int index = 0;
        if (set1.size() <= set2.size()){
            result = new int[set1.size()];
            for (Integer n : set2) {
                if (set1.contains(n)){
                    result[index++] = n;
                }
            }
        }else {
            result = new int[set2.size()];
            for (Integer n : set1) {
                if (set2.contains(n)){
                    result[index++] = n;
                }
            }
        }
        System.out.println(Arrays.toString(result));
        return Arrays.copyOf(result, index);
    }

}

/**
 * 官方题解
 */
class Solution {
    public int[] set_intersection(HashSet<Integer> set1, HashSet<Integer> set2) {
        int [] output = new int[set1.size()];
        int idx = 0;
        for (Integer s : set1) {
            if (set2.contains(s)) {
                output[idx++] = s;
            }
        }

        return Arrays.copyOf(output, idx);
    }

    public int[] intersection(int[] nums1, int[] nums2) {
        HashSet<Integer> set1 = new HashSet<Integer>();
        for (Integer n : nums1) {
            set1.add(n);
        }
        HashSet<Integer> set2 = new HashSet<Integer>();
        for (Integer n : nums2) {
            set2.add(n);
        }

        if (set1.size() < set2.size()) {
            return set_intersection(set1, set2);
        } else {
            return set_intersection(set2, set1);
        }
    }
}

/**
 * 官方题解2
 */
class Solution2 {
    public int[] intersection(int[] nums1, int[] nums2) {
        HashSet<Integer> set1 = new HashSet<Integer>();
        for (Integer n : nums1) {
            set1.add(n);
        }
        HashSet<Integer> set2 = new HashSet<Integer>();
        for (Integer n : nums2) {
            set2.add(n);
        }

        //retainAll这个函数的作用是求交集，并把结果返回给调用者（set1）
        set1.retainAll(set2);
        System.out.println("set1 = " + set1);

        int [] output = new int[set1.size()];
        int idx = 0;
        for (int s : set1) {
            output[idx++] = s;
        }
        return output;
    }
}
